import sys
parse_table=[]
production_list=[]
production_count=0

def ckyparse(tagged_list,grammar):

    global production_count
    global parse_table
    global production_list

    production_count=0
    parse_table=[]
    production_list=[]
    
    ques_tag_pattern=""
    
    for i in tagged_list:
        ques_tag_pattern+=i[1]
        ques_tag_pattern+=" "

    ques_pattern=""
    
    for i in tagged_list:
        ques_pattern+=i[0]
        ques_pattern+=" "
    
    ques_list=ques_pattern.split()  
    ques_tag_list=ques_tag_pattern.split()
    length=len(ques_tag_list)
    
    #print ques_tag_list
    #raw_input()

    #initialize the parse_table
    for i in range(length+1):
        ml=[]
        for j in range(length+1):
            ml.append(-1)
        parse_table.append(ml)

    #first forloop of cky algorithm        
    for j in range(1,length+1):
        #table[j-1,j]<-{A|A -> words[j] E grammar
        parse_table[j-1][j]=[]
        production_list.append([{ques_tag_list[j-1]:ques_list[j-1]},[-1,-1]])
        parse_table[j-1][j].append(production_count)
        production_count+=1

        add_productions(parse_table[j-1][j],production_list[production_count-1],[production_count-1,-1],grammar)
    
        #print "curr prod list= ",curr_production_list
        #raw_input()

    
        #second forloop of cky algorithm
        for i in range(j-2,-1,-1):
            parse_table[i][j]=[]
        
            #third forloop of cky algorithm
            for k in range(i+1,j):
                blist=parse_table[i][k]
                clist=parse_table[k][j]
                B=[]
                C=[]
                for tmp in blist:
                    B.append({production_list[tmp][0].keys()[0]:production_list[tmp][1]})

                for tmp in clist:                    
                    C.append({production_list[tmp][0].keys()[0]:production_list[tmp][1]})

                for tmp in B:
                    for tmp1 in C:
                        key=tmp.keys()[0]
                        key1=tmp1.keys()[0]
            
                        two_val=[key,key1]
                        l=get_right_productions(two_val,grammar)
                        for tmp3 in l:
                            add_this_rule={tmp3:two_val}
                            production_list.append([add_this_rule,[tmp[key][0]+1,tmp1[key1][0]+1]])
                            parse_table[i][j].append(production_count)
                            production_count+=1
                            add_productions(parse_table[i][j],production_list[production_count-1],[production_count-1,-1],grammar)
    
        
    return [parse_table,production_list]


def add_productions(p_table_cell,production,offset,grammar):
    """ to do
    """
    to_check_production_lhs=production[0].keys()[0]
    to_check_production_rhs=production[0][to_check_production_lhs]
    global production_count
    
    for i in grammar:
        lhs=i.keys()[0]
        rhs=i[lhs]
        for j in rhs:
            if j==[to_check_production_lhs]:
                add_this_rule={lhs:j}
                production_list.append([add_this_rule,offset])
                p_table_cell.append(production_count)
                production_count+=1

                #call recursively
                add_productions(p_table_cell,production_list[production_count-1],[production_count-1,-1],grammar)
    return


def get_right_productions(rhslist,grammar):
    """ Returns 1 if A -> rhslist is present in the grammar..
    else, return 0.
    """
    ret_list=[]                                       
    for i in rhslist:
        if i== -1:
            return ret_list

    for i in grammar:
        lhs=i.keys()[0]
        rhs=i[lhs]
        for j in rhs:
            if j== rhslist:
                ret_list.append(lhs)

    return ret_list
